Machine vision images are made up of numerical arrays of data defining a color or gray level intensity for each pixel in a two dimensional grid. Industrial machine vision inspection systems typically employ gray level vision. In such systems, the gray level or light intensity level of each pixel is represented by a number from 0 to 255. Image analysis software tools are used to extract meaningful information from raw image data.
Various methods have been developed to recognize patterns, feature edges and contours for recognizing features or objects within an image.
One image analysis tool that is widely known for use in industry is called blob analysis. A blob analysis tool classifies image pixels as belonging to either an object or background and then joins the groups of pixels in each classification to represent discrete objects. The various moments of the connected objects are computed to determine the object's position, size and orientation. Blob tools can perform high speed image analysis with subpixel accuracy when used with images that include very little noise. However, the presence of touching or overlapping objects in an image and/or noise or image degradation prevents blob analysis tools from discriminating objects for inspection or identification. The range of potential applications for blob analysis is severely limited because the method of separating objects from backgrounds can only be performed in practice when objects of interest are either entirely brighter or entirely darker than the background.
Another common method of image analysis used in industry is referred to as template matching. Template matching methods require a training step wherein a model image or template of objects to be located is generated and stored. At run time, the template is compared with like-sized subsets of the image over a range of positions. The position having a greater match with the template is determined to be the position of the object in an image. A numeric representation of the degree of match can be generated and used for inspection purposes.
Early versions of template matching tools reassigned the value of each pixel to one of two states: bright or dark, with reference to a somewhat arbitrary threshold so that comparison operations were practical using processors that were available at the time. The thresholding step made subpixel accuracy impractical, by requiring machine operators to choose threshold values, and made results highly susceptible to variations in illumination and object reflectivity.
As faster processors became available, the limitations of template matching were overcome by using normalized correlation for the template comparison operation. Normalized gray scale correlation involves moving a gray scale image representing the object over the image in which the object must be found in order to determine a correlation peak indicating both the location of the object and the degree of match. Normalized correlation methods do not require objects to be separated from their background by brightness and are very tolerant of various forms of image degradation. Normalized correlation also tolerates touching or overlapping objects in an image.
Due to its advantages over template matching and blob analysis, normalized correlation methods became the dominant method for pattern matching in industry and in particular in the semiconductor manufacturing and electronics assembly fields. Unlike blob analysis, however, normalized correlation methods do not have the ability to tolerate and measure variations in orientation and size. Variations of a few degrees of rotation or a few percent in object size will cause normalized correlation methods to render inaccurate results.
The normalized correlation method also suffers diminished performance when used to identify 3-D objects in an image. This performance degradation is due to shading variations that depend on illumination direction, target surface orientations and shadows. These limitations make normalized correlation methods unsuitable for use in typical robotic assembly equipment where recognition of 3-D objects is required.
A method of geometric pattern matching was developed to overcome the limitations of normalized correlation by representing objects as geometric shapes independent of shading and independent of a discrete grid. The geometric pattern matching method can tolerate and measure wide variations in orientation and size of objects in an image, can be performed with high speed and high accuracy, and is able to tolerate severe shading variations. An exemplary geometric pattern matching tool called PatMax is available from Cognex Corporation of Natick, Mass.
The geometric pattern matching technology used in PatMax includes algorithms for feature detection, training, affine searching, pose refinement, and inspection. Feature detection produces a geometric description of object boundaries as an ordered list of boundary points that lie along contours separating dissimilar regions in the image. Unlike traditional edge detection, which simply marks certain pixels as edges, each boundary point specifies positions and orientation as real valued coordinates. PatMax uses a range of granularity that is appropriate for each particular image. Geometric descriptions of objects only make sense when the proper granularity is chosen. By selecting the appropriate granularity, PatMax is able to find objects whose edges may be discontinuous at a granularity which would make use of a traditional edge detector impossible.
PatMax performs a training procedure to choose the range of granularity that makes sense for objects to be found and then to select features at each of the various chosen granularities to represent the object. The task of choosing granularities and selecting features during a training procedure is quite challenging and can be a source of considerable error when humans make these choices. PatMax fully automates these tasks and allows human overrides only as a last resort for unusual cases.
The geometric descriptions of objects produced by feature detection can be translated, rotated, scaled, stretched and otherwise transformed with no loss in fidelity. PatMax uses a six degree of freedom affine transform which includes two degrees of freedom of translation and one each of rotation, scale, aspect ratio and skew. Each non-translation degree of freedom is specified as either a fixed value or a range of values to be searched. A fixed value for a degree of freedom allows a transformed version of the trained pattern to be found with no time penalty and no need to train extra patterns. For example, a single square pattern can be trained and used to find rectangular objects at a variety of known sizes and shapes by setting appropriate fixed values for the scale degrees of freedom.
PatMax next performs a pose refinement algorithm to compute translation, orientation and scale of an object to extremely high accuracy. Algorithms such as those used by PatMax that locate objects having various scales and orientations are commonly referred to as RISI (rotation invariant scale invariant) tools.
In order to recognize an object in an image, analysis tools, such as PatMax, must first be trained by acquiring and storing a model of a representative object. The model can be developed as an image of an actual object or can be synthetically constructed using CAD tools. During run time operation, the machine vision system acquires an image that may include the object of interest at any scale or orientation relative to the viewing device. The analysis tools will recognize the object in the image and compute the degree of rotation, scale and translation of the object in the image relative to the trained model. This computation is sometimes referred to as an alignment of the object.
It is often desirable to verify that specified dimensions of an object as measured in the image following an alignment are within pre-specified ranges. These measurements commonly referred to as gauging are typically performed by extracting pairs of feature positions in the image for example by manually placing caliper tools, or by using a search method to locate distinctive patterns, and then measuring the distance between the pairs in order to compare them to allowed ranges.
One known method of measuring the distance between pairs in a machine vision image can be performed using CALIPER TOOLS™ available from Cognex Corporation of Natick, Mass. CALIPER TOOLS™ is a vision tool for measuring the width of objects, the location of edges or features, and the location and spacing of pairs of edges in images. CALIPER TOOLS™ differs from other vision tools in that it requires users to know the approximate location and characteristics of the feature or edges that are to be located or measured. CALIPER TOOLS™ is typically used to develop detailed information about the locations of features within an object.
CALIPER TOOLS™ supports two methods of locating edges or edge pairs in an image: an edge mode in which edge peaks are detected using a simple 1-D kernel; and a correlation mode in which correlation peaks between a 1-D sample image and a 1-D reference image are located. Once a user has determined the location and orientation of the edge or edge pair of interest within an image he must perform the following steps to apply CALIPER TOOLS™. First, the user must specify a region enclosing the edges or edge pairs of interest. Then, for edge mode, the user must select a filter size and contrast threshold that isolates the edges of interest and define an edge model that describes the edge or edge pair of interest. For correlation mode, the user must supply a one-dimensional reference image. For either mode, the user must define the scoring methods for scoring edge pattern candidates within the image. Finally, the user can apply CALIPER TOOLS™and interpret the results.
Another Cognex product, called Checkpoint, provides various tools like a caliper for measuring points and lines, gauging tools for verifying point-point and point-line distances and tools for gauging angles and arcs. The Checkpoint tools also allow the user to set tolerances on distances between points and lines that are measured using other vision tools.
Another software tool, called Sherlock, available from Coreco Imaging Inc. of Bedford Mass., can be used to perform caliper type measurements of distances between points in an image.
Various RISI inspection tools have also been used to perform gauging by determining a linear mapping from the object to the image, interpolating to estimate specified gauging points and computing the distance between those points. The linear interpolation approach only works well for rigid 2D objects that translate within the imaging plane, rotate about the line of sight, or scale due to movement along the line of sight. Rotations of 2D objects out of the imaging plane, or 3D objects undergoing arbitrary translation with no rotation out of the plane, can only be described by a linear transformation when the imaging optics approximate an orthographic projection with scale, which typically occurs only when the object is at a large distance from the imaging system relative to its size. A known (pre-measured) calibration mapping might be used to extend the capabilities of linear interpolation by correcting for perspective effects; however, non-linear deformations of the objects, such as those due to manufacturing variances, cannot be corrected by such methods.
Gauging has also been performed by applying separate alignment tools to find object features then measuring the distance between them. For example, Cognex Checkpoint tools and another Cognex product called Insight both require users to perform gauging in this manner. The method of applying separate alignment tools to find object features disadvantageously requires users to manually choose stable alignment models for the portions of the object from which gauging points are measured. This method requires the configuration of additional vision tools in an application specific fashion and usually requires extensive knowledge of machine vision, especially when the features of interest do not lie directly on any stable portions.
Another method of gauging has been performed by aligning pre-defined sub-models of an object by specifying “salient dimensions” of the object as defined in U.S. patent application Ser. No. 09/054,968 by Sarachik, Bachelder, Marrion and Chang (hereinafter referred to as “the Sarachik Application”) which is hereby incorporated by reference in its entirety.
The Sarachik Application discloses a method of locating an object within a client region, where the object has a plurality of portions. The method includes defining a full geometric model of the object; defining a plurality of geometric sub-models of the object; determining coarse candidate poses of the object within the region using an image of the region and the full geometric model of the object; determining the fine pose of each of a plurality of portions of the object using the coarse candidate poses of the object within the region, and at least some of said geometric sub-models, to provide a plurality of object portion fine poses within the region; and then determining the fine poses of the object within the region using said plurality of object portion fine poses. The invention disclosed in the Sarachik Application allows geometric descriptions of objects (such as resistor chips, ball grid array packages, flip chips, etc.) to be specified in an arbitrary coordinate system, such as a physical (real world) coordinate system. This allows the same model to be used when locating the object within the physical world over a wide range of imaging conditions. The invention provides a powerful method for finding objects in images that is efficient in both memory space and computational time. This technique, however, is limited to locating geometric sub-models of an object when the approximate pose of the object is already known. Furthermore, it provides no method for automatically determining a set of sub-models for an object so that gauging can be performed.
U.S. patent application Ser. No. 09/212,844 entitled “Improved Object Image Search Using Validated Sub-Model Poses” by Bachelder and Sarachik (hereinafter referred to as “the Bachelder Application”) which is hereby incorporated by reference in its entirety discloses refinements to the method taught by the Sarachik Application.
The Bachelder Application discloses a method for finding a pose of a geometric model of an object within an image of a scene containing the object that includes providing sub-models of the geometric model; and providing found poses of the sub-models in the image. The method also includes selecting sub-models of the geometric model based on pre-fit selection criteria and/or post-fit selection criteria so as to provide selected sub-models of the geometric model. Thus, the invention disclosed in the Bachelder Application automatically removes, disqualifies, or disables found sub-model poses when they fail to satisfy certain user-specified requirements. Examples of such requirements include thresholds on deviations between the found sub-model pose, as well as limits on the sub-model. The remaining, validated sub-models can then be used to re-compute a more accurate fit of the model to the image. The method can also ensure that the new fit conforms to user-specified requirements, such as requiring that skew or aspect components of the final model pose be below some user-specified threshold. The invention disclosed in the Bachelder application not only allows sub-model outliers to be discarded so as to obtain a more close-fitting model pose, but also reduces the possibility of “false positives”, i.e., returning a model pose when the model does not exist within the image.
U.S. patent application Ser. No. 09/285,626 entitled “Fiducial Mark Search Using Sub-Models” by Roberts and Sarachik (hereinafter referred to as “the Roberts Application”) which is hereby incorporated by reference in its entirety also provides further refinement to the methods taught by the Sarachik Application.
The Roberts Application discloses a method for finding a pose of a geometric model of a fiducial mark within an image of a scene containing the fiducial mark. The method includes receiving input from a user including geometric model shape information and geometric model dimensions, selecting a pre-defined model being parameterized by the geometric model dimensions; and then using the pre-defined model to find an image of the fiducial mark in the image of the scene. The act of selecting a pre-defined model having sub-models includes pre-defining a model such that the sub-models and the relationships among the sub-models are selected by exploiting knowledge of features and properties of the fiducial sought so as to provide more accurate location of the fiducial. The invention disclosed in the Roberts Application provides enhanced ease of use of a sub-model based search method by requiring only the shape and dimensions of the fiducial sought. An appropriate model and its sub-models are automatically provided. The model and its sub-models are particularly appropriate to the application when they are based on knowledge of the variability of the fiducial and other aspects of the behavior of the fiducial throughout a manufacturing process, for example.
U.S. patent application Ser. No. 09/140,124 to Sarachik entitled Gauging Using Sub-Model Poses which is hereby incorporated by reference disclosed the use of sub-models to perform gauging. However the method disclosed by this application simplistically requires manual specification of sub-models for each gauging point.
Each of the referenced U.S. patent applications discloses methods that require substantial user knowledge of vision systems to select and evaluate various sub-models and/or sub-model parameters. Such knowledge is beyond that which should be required to perform simple gauging tasks. The human input required by these methods creates opportunity for error and increases the time and expense of making machine vision gauging measurements.